package demo1;

import java.sql.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        private  char val ;
        private TreeNode left ;
        private TreeNode right ;

        public TreeNode(char val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return this.val + " " ;
        }
    }

    public TreeNode createTree() {    //创造一个二叉树
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        TreeNode node7 = new TreeNode('G');
        TreeNode node8 = new TreeNode('H');
        node1.left = node2 ;
        node1.right = node3 ;
         node2.left = node4 ;
        node2.right = node5 ;
        node3.left = node6 ;
        node3.right = node7 ;
        node5.right = node8;
        return  node1 ;
    }
    public List<TreeNode> preOrder(TreeNode root){   // 先序遍历
           List<TreeNode> ret = new ArrayList<>();
           if(root == null) return ret ;
           ret.add(root);
           List<TreeNode> leftTree  = preOrder(root.left);
           ret.addAll(leftTree);
           List<TreeNode> rightTree = preOrder(root.right);
           ret.addAll(rightTree);
           return ret ;
    }
    public List<TreeNode>  inOrder(TreeNode root){   // 中序遍历
        List<TreeNode> ret = new ArrayList<>();
        if(root == null) return ret ;
        List<TreeNode> leftTree  = inOrder(root.left);
        ret.addAll(leftTree);
        ret.add(root);
        List<TreeNode> rightTree = inOrder(root.right);
        ret.addAll(rightTree);
        return ret ;
    }
    public List<TreeNode> postOrder(TreeNode root){   //后序遍历
        List<TreeNode> ret = new ArrayList<>();
        if(root == null) return ret ;
        List<TreeNode> leftTree  = postOrder(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree = postOrder(root.right);
        ret.addAll(rightTree);
        ret.add(root);
        return ret ;
    }
    public int nodeSize(TreeNode root){  // 返回树的结点个数
        if(root == null) return 0 ;
        return nodeSize(root.left) + nodeSize(root.right) + 1 ;

    }
    //获取叶子节点个数
    public int getLeafNodeCount(TreeNode root){
        if(root == null) return 0 ;
        if(root.left == null && root.right == null) return 1 ;
         return  getLeafNodeCount(root.left) + getLeafNodeCount(root.right) ;
    }

    //获取第k层的结点个数 ；
    public int getKLeveNodeCount(TreeNode root , int k){
        if(root == null || k < 1 ) return 0 ;
        if(k == 1) return 1 ;
        return getKLeveNodeCount(root.left , k-1) + getKLeveNodeCount(root.right , k- 1) ;
    }

    //获取树的高度
    public int getHigh(TreeNode root){
        if(root == null) return 0 ;
        int leftTreeHigh = getHigh(root.left);
        int rightTreeHigh = getHigh(root.right);
        return leftTreeHigh > rightTreeHigh ? leftTreeHigh + 1 : rightTreeHigh + 1 ;
    }

    //检测值为key的元素是否存在 ；
    public boolean find(TreeNode root , int key){
        if(root == null) return false ;
        if(root.val == key){
            return true ;
        }
        return find(root.left , key) || find(root.right , key) ;
    }



    //各种方法


    //返回值为value的元素
    public TreeNode findNode(TreeNode root , int val){
        if(root == null) return  null ;
        if(root.val == val) return root ;
        TreeNode leftTree = findNode(root.left , val) ;
        TreeNode rightTree = findNode(root.right ,val);
        if(leftTree != null) return leftTree ;
        if(rightTree != null ) return rightTree ;
        return null ;
    }

    // 判断两棵树是否相同 。 时间复杂度 Min( m  , n)  假设一颗树m个结点 ，一颗n个
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true ;
        if(p == null || q == null) return false ;

        if(p.val != q.val){
            return false ;
        }
        return isSameTree(p.left , q.left) &&
                isSameTree(p.right , q.right) ;

    }
    // 判断是否 是root 的子树 ；  时间复杂度 O( rot * sumRoot) ;
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null ) return false ;         //为了避免 root为空 ，而下面的left 导致的空指针 ；
        if(isSameTree(root , subRoot)) return true ;

        return isSubtree(root.left ,subRoot) ||
                isSubtree(root.right , subRoot) ;
    }

    //反转二叉树，左右结点互换
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null ;
        TreeNode tmp = root.left ;
        root.left = root.right ;
        root.right = tmp  ;
        invertTree(root.left);
        invertTree(root.right) ;

        return root ;
    }

    //判断是否平衡二叉树 ，因为每个节点都去数他的高度 ，会有重复计算的问题 ；
    // 我已经算过子树的高度了，但是 我递归过去 又算一遍 ；
    // getHigh的复杂度为 O(n) ;所有他的时间复杂度为 O(n的平方） ;
    public boolean isBalanced1(TreeNode root) {
        if(root == null) return true ;
        int leftTree = getHigh(root.left) ;
        int rightTree = getHigh(root.right) ;
        if(Math.abs(leftTree - rightTree) > 1){
            return false ;
        }
        return isBalanced1(root.left) &&
                isBalanced1(root.right) ;
    }

    //判断是否为平衡二叉树 ；
    // getHigh2 在得到子树的高度时顺便判断 高度差是否大于1 ；
    // 这样 在计算子树的高度的时候顺便判断了所有子树是否为平衡二叉树 ；
    // 这样的 复杂度就达到 O(n) ;
    public boolean isBalanced2(TreeNode root) {
        if(root == null) return true ;
       return getHigh2(root) >= 0;
    }
    public int getHigh2(TreeNode root){
        if(root == null) return 0 ;
        int leftH = getHigh(root.left) ;
        int rightH = getHigh(root.right) ;
        if(leftH>=0 && rightH>=0 &&
                Math.abs(leftH - rightH) <= 1){
            return Math.max(leftH , rightH) +1 ;
        }
        return -1 ;
    }

    //判断二叉树是否对称
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true ;
        return isSymmetricChild(root.left , root.right) ;
    }
    public boolean isSymmetricChild(TreeNode p  , TreeNode q){
        if(p == null && q == null) return true ;
        if(p == null || q == null) return false ;
        if(p.val != q.val){
            return false ;
        }
        return isSymmetricChild(p.left , q.right) &&
                isSymmetricChild(p.right , q.left) ;
    }



    //二叉树的分层遍历
    public void levelOrder(TreeNode root){
       if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>() ;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + "  ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

}









